Tập phổ biến là gì? Các bài nghiên cứu khoa học liên quan

Giới thiệu về tập phổ biến

Trong khai phá dữ liệu, đặc biệt là trong lĩnh vực phân tích giao dịch, khái niệm "tập phổ biến" (frequent itemset) đóng vai trò trung tâm. Một tập phổ biến là một nhóm các mục (items) thường xuyên xuất hiện cùng nhau trong một số lượng lớn các giao dịch của một cơ sở dữ liệu. Đây là thành phần cốt lõi để phát hiện các mẫu liên kết giữa các hành vi, sự kiện hoặc lựa chọn của người dùng.

Ví dụ trong bán lẻ, nếu nhiều khách hàng thường xuyên mua bánh mì và bơ đậu phộng cùng lúc, thì tập gồm hai mục này sẽ được xem là một tập phổ biến. Các hệ thống gợi ý sản phẩm, quảng cáo động và tối ưu hóa kho hàng đều dựa vào việc phân tích các tập phổ biến như vậy để ra quyết định.

Tập phổ biến là khái niệm nền tảng cho nhiều thuật toán khai phá dữ liệu nổi bật như:

• Apriori – Phát hiện tập phổ biến bằng phương pháp sinh ứng viên và kiểm tra.
• FP-Growth – Rút ngắn thời gian khai phá bằng cách sử dụng cấu trúc cây FP-tree.
• ECLAT – Khai thác hiệu quả theo hướng dọc bằng phép giao tập giao dịch.

Phân tích tập phổ biến không chỉ được ứng dụng trong thương mại điện tử mà còn mở rộng sang các lĩnh vực như y học (phân tích triệu chứng đi kèm), tài chính (phát hiện hành vi gian lận), và an ninh mạng (xác định mẫu truy cập bất thường).

Định nghĩa hình thức

Một cách chính xác hơn, tập phổ biến được định nghĩa trong ngữ cảnh một cơ sở dữ liệu giao dịch $D$, với mỗi giao dịch là một tập hợp các mục thuộc tập mục tổng quát $I$. Một tập con $X \subseteq I$ được xem là phổ biến nếu tần suất xuất hiện của nó trong cơ sở dữ liệu đạt ít nhất một ngưỡng tối thiểu gọi là ngưỡng hỗ trợ (minimum support threshold), thường ký hiệu là $\text{minsup}$.

Độ hỗ trợ (support) của tập mục $X$ được tính bằng tỉ lệ số giao dịch trong đó $X$ xuất hiện chia cho tổng số giao dịch trong cơ sở dữ liệu:

$\text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|}$

Một ví dụ cụ thể: giả sử cơ sở dữ liệu có 10.000 giao dịch, và tập mục \{sữa, bánh mì\} xuất hiện trong 1.500 giao dịch. Khi đó:

$\text{support}(\{sữa, bánh mì\}) = \frac{1500}{10000} = 0.15$

Nếu ngưỡng hỗ trợ được đặt là 0.1 (10%), thì \{sữa, bánh mì\} là một tập phổ biến vì 15% > 10%.

Việc lựa chọn giá trị phù hợp cho $\text{minsup}$ rất quan trọng: nếu quá cao thì sẽ bỏ lỡ nhiều mẫu tiềm năng; nếu quá thấp thì dẫn đến quá nhiều tập phổ biến dư thừa.

Ý nghĩa trong khai phá dữ liệu

Khai phá tập phổ biến không đơn thuần là tìm ra các kết hợp thường gặp trong dữ liệu, mà là quá trình rút ra các tri thức có thể hành động được từ dữ liệu thô. Tập phổ biến là bước đầu tiên trong chuỗi các phân tích như tìm luật kết hợp, phân cụm giao dịch, và phát hiện dị thường.

Từ các tập phổ biến, ta có thể xây dựng các luật kết hợp (association rules) dưới dạng: X → Y, nghĩa là nếu khách hàng mua X thì có xác suất cao họ cũng sẽ mua Y. Luật này sẽ được xem xét nếu tập $X \cup Y$ là phổ biến. Đây là phương pháp nền trong nhiều ứng dụng như hệ thống khuyến nghị.

Bảng dưới đây minh họa mối liên hệ giữa tập phổ biến và luật kết hợp:

Tập mục (X)	Tập mục (Y)	Tập phổ biến (X ∪ Y)?	Luật hợp lệ?
{trứng}	{bacon}	Có	Có
{sữa}	{bánh quy}	Không	Không
{bánh mì, bơ}	{mứt}	Có	Có

Ngoài ra, tập phổ biến còn được sử dụng trong kiểm kê kho, khi ta muốn biết các nhóm sản phẩm nào nên được đặt gần nhau để tối ưu hóa bố trí cửa hàng. Trong an ninh mạng, phát hiện các lệnh hoặc hành động thường xuyên đi kèm có thể giúp phân loại hành vi người dùng hoặc phát hiện hoạt động đáng ngờ.

Phân loại tập phổ biến

Không phải tất cả tập phổ biến đều hữu ích như nhau. Các nhà nghiên cứu và kỹ sư dữ liệu thường phân loại tập phổ biến theo các tiêu chí nhất định để rút gọn không gian tìm kiếm và tránh trùng lặp thông tin.

Ba loại tập phổ biến chính thường được quan tâm:

• Tập phổ biến tối đại (Maximal Frequent Itemset): là tập phổ biến không có bất kỳ siêu tập phổ biến nào. Chúng giúp giảm kích thước đầu ra và thường dùng trong khai phá dữ liệu lớn.
• Tập phổ biến đóng (Closed Frequent Itemset): là tập phổ biến mà không có siêu tập nào của nó có cùng độ hỗ trợ. Chúng cho phép giữ lại đầy đủ thông tin hỗ trợ mà không bị trùng lặp.
• Tập phổ biến tối tiểu (Minimal Frequent Itemset): là những tập phổ biến nhỏ nhất (về số lượng phần tử) vẫn thỏa điều kiện hỗ trợ. Tuy không phổ biến bằng hai loại trên nhưng có thể hữu ích khi phân tích các quan hệ nền tảng.

Ví dụ, xét cơ sở dữ liệu đơn giản sau:

Giao dịch	Các mục
T1	{a, b, c}
T2	{a, b}
T3	{a, c}
T4	{b, c}

Nếu ngưỡng hỗ trợ là 50%, các tập phổ biến gồm {a}, {b}, {c}, {a,b}, {a,c}, {b,c}. Trong đó:

• {a, b, c} không phải là phổ biến vì chỉ xuất hiện 1 lần.
• {a, b} là một tập phổ biến đóng nếu không có siêu tập nào khác của nó có cùng độ hỗ trợ.
• {a, b} cũng có thể là tập phổ biến tối đại nếu không có siêu tập phổ biến nào của nó.

Thuật toán khai thác tập phổ biến

Việc tìm kiếm tập phổ biến trong một cơ sở dữ liệu lớn không thể thực hiện bằng cách kiểm tra mọi tổ hợp có thể – do không gian tìm kiếm tăng theo cấp số mũ với số lượng mục. Vì vậy, các thuật toán tối ưu đã được phát triển nhằm rút ngắn thời gian và giảm chi phí tính toán.

Các thuật toán tiêu biểu trong lĩnh vực này bao gồm:

• Apriori: Sử dụng tính chất chống đơn điệu (downward closure property), nghĩa là nếu một tập mục không phổ biến thì mọi siêu tập của nó cũng không thể phổ biến. Thuật toán lặp lại quá trình sinh tập ứng viên và tính toán độ hỗ trợ, tuy nhiên gặp hạn chế khi số lượng ứng viên lớn.
• FP-Growth: Không tạo tập ứng viên. Thay vào đó, nó xây dựng cấu trúc FP-tree nén dữ liệu và khai thác theo phương pháp chia để trị. FP-Growth thường nhanh hơn Apriori trong thực tế.
• ECLAT: Dựa trên giao cắt tập giao dịch (transaction ID sets), xử lý dữ liệu theo chiều dọc. Hiệu quả hơn khi dữ liệu có mật độ cao.

Bảng sau tóm tắt so sánh một số đặc điểm kỹ thuật giữa ba thuật toán chính:

Thuật toán	Chiến lược khai thác	Ưu điểm	Nhược điểm
Apriori	Dựa trên sinh & kiểm tra ứng viên	Dễ hiểu, dễ triển khai	Chi phí tính toán lớn với dữ liệu lớn
FP-Growth	Dựa trên cấu trúc FP-tree	Tiết kiệm bộ nhớ, không cần ứng viên	Khó triển khai, cần quản lý đệ quy
ECLAT	Giao cắt tập giao dịch theo chiều dọc	Hiệu quả với tập dữ liệu dày	Không thích hợp cho dữ liệu phân tán

Tùy vào đặc điểm dữ liệu (kích thước, mật độ, định dạng), các nhà phân tích có thể lựa chọn thuật toán phù hợp để tối ưu hóa hiệu năng xử lý.

Ứng dụng thực tiễn

Việc phát hiện các tập phổ biến có giá trị thực tiễn cao, đặc biệt trong các hệ thống dự báo và ra quyết định dựa trên dữ liệu. Một số ứng dụng nổi bật có thể kể đến:

• Phân tích giỏ hàng (Market Basket Analysis): Tìm ra các sản phẩm thường được mua cùng nhau để tối ưu vị trí trưng bày, thiết kế gói sản phẩm hoặc chiến lược khuyến mãi.
• Hệ thống khuyến nghị: Gợi ý sản phẩm/dịch vụ dựa trên các mẫu hành vi người dùng tương tự trong lịch sử.
• Phát hiện gian lận: Xác định các hành vi lặp lại bất thường trong tài khoản hoặc giao dịch tài chính.
• Chẩn đoán y khoa: Phát hiện các cụm triệu chứng thường xuất hiện đồng thời giúp hỗ trợ chẩn đoán và điều trị.

Ví dụ: một nền tảng thương mại điện tử như Amazon sử dụng dữ liệu tập phổ biến để tạo phần “Frequently Bought Together”. Trong y học, các tập triệu chứng phổ biến giúp phát triển hệ thống hỗ trợ chẩn đoán sớm bệnh lý.

Thách thức trong việc khai phá tập phổ biến

Dù tập phổ biến là công cụ mạnh mẽ, quá trình khai phá vẫn gặp phải nhiều thách thức lớn. Một trong những khó khăn chính là vấn đề bùng nổ tổ hợp – số lượng tập mục tăng rất nhanh khi số mục trong cơ sở dữ liệu tăng.

Các vấn đề phổ biến:

1. Kích thước dữ liệu lớn: Khi số lượng giao dịch hàng triệu hoặc hàng tỷ, việc tính toán độ hỗ trợ trở nên tốn tài nguyên.
2. Ngưỡng hỗ trợ thấp: Nếu đặt minsup thấp để không bỏ sót các mẫu hiếm, thuật toán sẽ phải xử lý số lượng lớn tập phổ biến, gây quá tải.
3. Tập phổ biến dư thừa: Nhiều tập gần giống nhau có thể gây khó khăn trong việc phân tích và sử dụng.
4. Dữ liệu phân tán: Khi dữ liệu được lưu trữ trên nhiều node (ví dụ Hadoop), việc đồng bộ và tính toán tập phổ biến cần cơ chế phức tạp hơn.

Ngoài ra, khai phá tập phổ biến có thể không phù hợp với các dữ liệu không có cấu trúc hoặc liên tục (như văn bản hoặc thời gian thực), đòi hỏi kỹ thuật bổ sung như chuẩn hóa, rút trích đặc trưng hoặc xử lý phân cụm.

Chiến lược tối ưu và cải tiến

Trước những thách thức nêu trên, nhiều hướng nghiên cứu và kỹ thuật đã được phát triển nhằm cải thiện hiệu quả và khả năng ứng dụng của việc khai phá tập phổ biến.

Một số chiến lược chính:

• Nén dữ liệu bằng cấu trúc cây: FP-tree, H-Mine tree cho phép tổ chức dữ liệu hiệu quả hơn, giảm số lần quét.
• Khai phá dữ liệu hiếm: Trong nhiều tình huống, các mẫu hiếm nhưng lại quan trọng, ví dụ trong phát hiện gian lận. Do đó, các kỹ thuật như Rare Itemset Mining được nghiên cứu.
• Khai phá dữ liệu động: Với dữ liệu thời gian thực, cần phát triển các thuật toán có khả năng cập nhật liên tục như Lossy Counting, Landmark window.
• Song song hóa và phân tán: Sử dụng nền tảng như Apache Spark hoặc MapReduce để xử lý khối lượng dữ liệu cực lớn trong thời gian hợp lý.

Những cải tiến này đã mở rộng phạm vi ứng dụng thực tế của tập phổ biến và giúp tích hợp dễ dàng hơn vào các hệ thống lớn và đa dạng.

Tập phổ biến trong học máy và AI

Tập phổ biến thường được xem là một kỹ thuật phân tích thống kê, tuy nhiên trong bối cảnh học máy hiện đại, nó đóng vai trò quan trọng trong nhiều pipeline xử lý dữ liệu và trí tuệ nhân tạo.

Một số ứng dụng trong học máy:

• Chọn đặc trưng (feature selection): Các tập phổ biến cung cấp thông tin về các nhóm thuộc tính thường đi cùng nhau, giúp giảm chiều dữ liệu.
• Phân cụm giao dịch: Dựa trên các mẫu phổ biến, có thể nhóm các người dùng có hành vi tương tự.
• Học không giám sát: Trong các bài toán không có nhãn, tập phổ biến có thể giúp phát hiện cấu trúc nội tại của dữ liệu.

Trong AI ứng dụng, như chatbot thương mại, hệ thống trợ lý ảo, các tập phổ biến cũng giúp dự đoán và phản hồi theo mẫu hành vi phổ biến của người dùng trước đó.

Tài liệu tham khảo

1. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference.
2. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD.
3. Zaki, M. J., & Hsiao, C.-J. (2002). CHARM: An efficient algorithm for closed itemset mining. Journal of Intelligent Information Systems.
4. KDnuggets – Frequent Itemsets
5. Analytics Vidhya – Association Rule Mining
6. Towards Data Science – Frequent Itemsets and Association Rules
7. Apache Spark MLlib – Frequent Pattern Mining